/**
 * @a https://leetcode.cn/problems/insert-interval/description/
 */

#include "../common.h"

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ret;
        int cur = 0, sz = intervals.size();
        while(cur < sz && intervals[cur][1] < newInterval[0]){
            ret.push_back(intervals[cur++]);
        }

        for(;cur < sz && intervals[cur][0] <= newInterval[1];++cur){
            newInterval[0] = min(intervals[cur][0], newInterval[0]);
            newInterval[1] = max(intervals[cur][1], newInterval[1]);
        }
        ret.push_back(newInterval);
        while(cur < sz) ret.push_back(intervals[cur++]);
        return ret;
    }
};